// 解题思路： 动态规划
// 判断条件，如果dp[i-1]dp[j+1] 是回文子串，如果dp[i] == dp[j] 那么dp[i][j]也是回文子串  最大长度加2  因此状态转移方程：P(i,j)=P(i+1,j−1)∧(Si​==Sj​)
// 回文子串的三种判断：
// 1.当length > 3 , 则上述判断 P(i,j)=P(i+1,j−1)∧(Si​==Sj​)
// 2.当length == 2 , 则P(i,i+1)=(Si==Si+1)
// 3.当length == 1 , 则 P(i,i) = true 



var longestPalindrome = function (s) {
    let n = s.length;
    let res = '';
    let dp = Array.from(new Array(n), () => new Array(n).fill(false));//初始化数组 
    // for (let i = 0; i < s.length; i++) {
    //     for (let j = 0; j < s.length; j++) {
    //         console.log(dp[i][j], '----')
    //     }
    // }
    for (let i = n - 1; i >= 0; i--) {//循环字符串
        for (let j = i; j < n; j++) {
            //dp[i][j]表示子串i～j是否是回文子串
            //回文子串必须满足s[i]，s[j]相等。并且向外扩展一个字符也相等，即dp[i+1][j-1]也是回文子串
            //j - i < 2表示子串小于等于1也是回文串
            dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]);
            //(j - i < 2 表示是length <= 2 的俩种情况 即legth==1,dp[i][i]一定为ture，length==2, dp[i][i+1]如果为true 则表示成功 )
            // 该段是本章算法的核心！！！
            // 并且当i = j 时， 会先辅助dp[i][j]成为true, 使得后面的判断dp[i+1][j-1] 成立

            if (dp[i][j] && j - i + 1 > res.length) {//当前回文子串比之前的大，更新最大长度
                res = s.substring(i, j + 1); //截取子串
            }
        }
    }
    return res;
};
console.log(longestPalindrome('aaaqabaqccc'))